import bisect
from collections import deque
import heapq
from typing import List

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution(object):
    def count_range_sum(self, nums, lower, upper):
        presum = [0]
        for num in nums:
            presum.append(presum[-1] + num)
        def merge_sort(l, r):
            if l == r:
                return 0
            mid = (l + r) // 2
            cnt = merge_sort(l, mid) + merge_sort(mid + 1, r)
            i = j = mid + 1
            for left in presum[l:mid + 1]:
                while i <= r and presum[i] - left < lower:
                    i += 1
                while j <= r and presum[j] - left <= upper:
                    j += 1
                cnt += j - i
            presum[l:r + 1] = sorted(presum[l:r + 1])
            return cnt
        return merge_sort(0, len(presum) - 1)
    
    def getSkyline(self, buildings):
        """
        :type buildings: List[List[int]] 存储建筑物坐标的双重嵌套列表
        :rtype: List[List[int]]  
        """
        # initialize the variables
        # 初始化变量
        skyline = []       # 天际线 
        i = 0              # 用来迭代当前建筑
        n = len(buildings) # 列表的长度
        liveBuildings = [] # 当前地方仍然存在的建筑物
        # 迭代所有的建筑
        while i < n or liveBuildings:
            # 如果当前区域没有可见的建筑物或者下一个开始也没有建筑再在当前建筑迭代结束之后
            if not liveBuildings or (i < n and buildings[i][0] <= -liveBuildings[0][1]):
                # 将当前的x坐标设置为下一个建筑的起点
                x = buildings[i][0]

                # 遍历从当前x坐标开始的所有建筑
                while i < n and buildings[i][0] == x:
                    # 向堆中添加建筑物的高度和结束坐标
                    heapq.heappush(liveBuildings, (-buildings[i][2], -buildings[i][1]))
                    # 迭代到下一个建筑
                    i += 1
            else:
                # 将当前的x坐标设置为当前建筑物的末端
                x = -liveBuildings[0][1]

                # 移除所有在当前x坐标之前结束的建筑
                while liveBuildings and -liveBuildings[0][1] <= x:
                    heapq.heappop(liveBuildings)

            # 获得当前x坐标下建筑物的最大高度
            height = len(liveBuildings) and -liveBuildings[0][0]

            # 如果高度发生了变化，将新的点添加到天际线上
            if not skyline or height != skyline[-1][1]:
                skyline.append([x, height])

        return skyline


    # 简单的动态规划算法，时间复杂度为O(n^2)
    def lengthOfLIS_simple(self, nums, k):
        n = len(nums)
        dp = [1] * n
        for i in range(n):
            for j in range(i):
                if nums[i] > nums[j] and nums[i] - nums[j] <= k:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)

    # 分治算法示例代码，时间复杂度为O(nlogn)
    def lengthOfLIS_normal(self, nums: list[int], k: int) -> int:
        n = len(nums)
        positions = list(range(n))
        positions.sort(key=lambda x: (nums.__getitem__(x), -x))
        dp = [1] * n

        def DivideAndConquer(l, r, positions):
            dac = DivideAndConquer
            if l == r:
                return
            m = (l + r) >> 1
            left, right = [], []
            for pos in positions:
                if pos <= m:
                    left.append(pos)
                else:
                    right.append(pos)
            dac(l, m, left)
            #
            que = deque()
            for pos in positions:
                if pos <= m:
                    while que and dp[pos] >= dp[que[-1]]:
                        que.pop()
                    que.append(pos)
                else:
                    while que and nums[que[0]] < nums[pos] - k:
                        que.popleft()
                    if que: dp[pos] = max(dp[pos], dp[que[0]] + 1)
            #
            dac(m + 1, r, right)

        DivideAndConquer(0, n - 1, positions)
        return max(dp)

    # 二分查找优化的动态规划算法，时间复杂度为O(nlogn)
    def lengthOfLIS_best(self, nums: list[int], k: int) -> int:
        dp = [1]
        value = [nums[0]]
        m = 1
        for i, v in enumerate(nums):
            if v > value[-1]:
                if value[-1] >= v - k:
                    dp.append(m + 1)
                    m += 1
                else:
                    dp.append(1)
                value.append(v)
            elif v <= value[0]:
                if value[0] == v:
                    continue
                dp.insert(0, 1)
                value.insert(0, v)
            else:
                left = bisect.bisect_left(value, v - k)
                right = bisect.bisect_right(value, v - 1)
                if left == right:
                    z = 1
                else:
                    z = max(dp[left:right]) + 1
                    m = max(m, z)
                idx = bisect.bisect_right(value, v) - 1
                if value[idx] == v:
                    dp[idx] = z
                else:
                    bisect.insort_right(value, v)
                    dp.insert(idx + 1, z)
        return max(dp)

    def find_median_sorted_arrays(self, nums1: list[int], nums2: list[int]) -> float:
        m, n = len(nums1), len(nums2)
        if m > n:
            nums1, nums2, m, n = nums2, nums1, n, m
        '''分割线左边的所有元素需要满足个数  m+(n-m+1)/2'''
        imin, imax, half_len = 0, m, (m + n + 1) // 2
        '''在 nums1 的区间 [0,m] 里查找恰当的分割线'''
        '''使得 nums1[i - 1] <= nums[j] && nums2[j - 1] <= nums[i]'''
        while imin <= imax:
            i = (imin + imax) // 2  # imin + (imax - imin) / 2  中间位置
            j = half_len - i
            if i < m and nums2[j - 1] > nums1[i]:
                '''下一轮搜索的区间[i + 1, imax]'''
                imin = i + 1
            elif i > 0 and nums1[i - 1] > nums2[j]:
                '''下一轮搜索的区间[imin, i]'''
                imax = i - 1
            else:
                '''满足要求'''
                if i == 0:
                    max_of_left = nums2[j - 1]
                elif j == 0:
                    max_of_left = nums1[i - 1]
                else:
                    max_of_left = max(nums1[i - 1], nums2[j - 1])
                '''个数为奇数个'''
                if (m + n) % 2 == 1:
                    return max_of_left  # 直接找到结果
                '''个数为偶数个'''
                if i == m:
                    min_of_right = nums2[j]
                elif j == n:
                    min_of_right = nums1[i]
                else:
                    min_of_right = min(nums1[i], nums2[j])
                return (max_of_left + min_of_right) / 2

                # mergeLists函数接收一个链表列表，并递归地将其分成两部分，直到只剩下一个或零个链表
                # 接收一个链表的数组并返回一个合并的链表

    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        # 检查数组是否为空
        if not lists:
            return None
        # 获取输入链表的长度，检查是否等于1，如果是，则返回第一个元素
        if len(lists) == 1:
            return lists[0]
        # 计算数组的中点，在链表数组的左右两半部分递归调用mergeKLists
        mid = len(lists) // 2
        left = self.mergeKLists(lists[:mid])
        right = self.mergeKLists(lists[mid:])
        # 合并
        return self.merge(left, right)

        # marge函数用于合并两个链表
        # 归并两个已排序好的算法

    def merge(self, l1, l2):
        # 检查输入链表中是否有一个为空，如果为空则返回另一个链表
        if not l1:
            return l2
        if not l2:
            return l1
        # 比较输入链表的第一个结点的值，并递归地在链表的其余结点上使用较小的值和整个其他链表调用merge
        # 最终返回合并后链表的头结点
        if l1.val < l2.val:
            l1.next = self.merge(l1.next, l2)
            return l1
        else:
            l2.next = self.merge(l1, l2.next)
            return l2